﻿using System;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using System.Collections.Generic;
using System.Linq;

namespace Algoritmia.Problems.CoinChange
{
    public class ChangeEnumerator<TState,TDecision>
    {
        private readonly Func<Lists.IList<TDecision>> _createList;
        private readonly Func<IEnumerable<TDecision>, Lists.IList<TDecision>> _copyList;

        public ChangeEnumerator(Func<IEnumerable<TDecision>,Lists.IList<TDecision>> createList = null)
        {
            _copyList = createList ?? (it => AlgoritmiaFactory.Lists<TDecision>.BuildDefault(it));
            _createList = () => _copyList(new TDecision[] { });
        }

        private IEnumerable<Lists.IList<TDecision>> Backtracking(TState state,
            IMoneyChangeForwardStateSpace<TState,TDecision> space, Lists.IList<TDecision> decisions)
        {
            if (space.IsFinal(state))
            {
                yield return _copyList(decisions);
            }

            foreach (var decision in space.Decisions(state))
            {
                decisions.Add(decision);
                var successor = space.Decide(state, decision);
                foreach (var result in Backtracking(successor, space, decisions))
                {
                    yield return result;
                }
                decisions.RemoveAt(decisions.Count - 1);
            }
        }

        public IEnumerable<Lists.IList<TDecision>> Enumerate(IMoneyChangeForwardStateSpace<TState, TDecision> stateSpace)
        {
            var decisions = _createList();
            var initial = stateSpace.InitialStates.First();
            return Backtracking(initial, stateSpace, decisions);
        }
    }

}
